package likou.offer;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/8/20  19:11
 */
public class _36 {
    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    public static void main(String[] args) {
        Node root = new Node(4);
        root.right = new Node(5);
        root.left = new Node(2);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        List<Integer> w = new ArrayList<>();
        w.add(1);
        w.add(8);
        System.out.println(w.toString());
//        treeToDoublyList(root);
    }
    public static Node treeToDoublyList(Node root) {
        Deque<Node> stack = new LinkedList<>();
        Node head = null;
        Node steep = null;
        while(root!=null||stack.size()!=0){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            if(head==null){
                steep = stack.pop();
                head = steep;
                root = steep.right;
                continue;
            }
            if (stack.size()!=0){
                root = stack.pop();
                steep.right = root;
                root.left = steep;
                root = root.right;
                steep = steep.right;
            }
        }
        steep.right = head;
        head.left = steep;

        return head;
    }
}
